package com.lun.swordtowardoffer2.c15;

public class FindRedundantConnection {
	
	private static final FindCircleNum FCN = new FindCircleNum();
	
	public int[] findRedundantConnection(int[][] edges) {
		int maxVertex = 0;
		
		for(int[] edge : edges) {
			maxVertex = Math.max(maxVertex, edge[0]);
			maxVertex = Math.max(maxVertex, edge[1]);
		}
		
		int[] fathers = new int[maxVertex + 1];
		
		for(int i = 1; i <= maxVertex; i++) {
			fathers[i] = i;
		}
		
		for(int[] edge : edges) {
			if(!FCN.union(fathers, edge[0], edge[1])) {
				return edge;
			}
		}
				
		return new int[2];
	}
}
